
#include "huffman.h"

/**
 *  功  能：
 *      创建一个霍夫曼树
 *  参  数：
 *      instr ：输入的字符串 
 *  返回值：
 *      成功 ：霍夫曼树的地址
 *      失败 ：NULL
 **/
htTree *build_huffmanTree(char *instr)
{
    int i;
    // 定义一个pQueu队列的头指针
    pQueue *huffmanQueue;
    // 分别用来记录256字符可能出现的次数
    int *probability = (int *)malloc(sizeof(int) * 256);
    memset(probability, 0, sizeof(int) * 256);

    // 统计需要编码的各个字符出现的次数
    for (i = 0; instr[i] != '\0'; i++)
        probability[(unsigned char)instr[i]]++;

    // 队列的初始化
    huffmanQueue = fqueue.create();

    // 填充队列，并且确保队列有序
    for (i = 0; i < 256; i++)
    {
        if (probability[i] != '\0')
        {
            // 哈夫曼树的节点
            htNode *node = (htNode *)malloc(sizeof(htNode));
            node->lchild = NULL;
            node->rchild = NULL;
            node->symbol = (char)i; // 下标
            // 插入队列
            fqueue.push(&huffmanQueue, (queueNode *)node, probability[i]);
        }
    }
    // 在填充队列的时候使用到出现的次数进行排序入队，现在队列创建完成，不需要了就释放度掉吧
    free(probability);
    // 生成哈夫曼树，在队列中只剩下一个元素的话，就是霍夫曼树的根节点了
    while (huffmanQueue->count != 1)
    {
        //生成新的节点的优先级，权值等，为前面两个节点的和
        int priority = huffmanQueue->node->priority;
        priority += huffmanQueue->node->next->priority;

        //新节点的左子树节点，右子树节点
        htNode *lchild = (htNode *)fqueue.pop(&huffmanQueue);
        htNode *rchild = (htNode *)fqueue.pop(&huffmanQueue);
        //创建一个新的节点
        htNode *newNode = (htNode *)malloc(sizeof(htNode));
        newNode->lchild = lchild;
        newNode->rchild = rchild;
        // 插入到队列中
        fqueue.push(&huffmanQueue, (queueNode *)newNode, priority);
    }

    // 创建一个霍夫曼树的根节点
    htTree *tree = (htTree *)malloc(sizeof(htTree));
    // 将队列中最后一个节点的值赋值给霍夫曼树的根节点
    tree->root = (htNode *)fqueue.pop(&huffmanQueue);
    // 销毁霍夫曼队列
    fqueue.destory(huffmanQueue);

    return tree;
}

/**
 *  功  能：
 *      递归销毁霍夫曼树中左右孩子节点
 *  参  数：
 *      node ：要销毁的霍夫曼树的节点
 *  返回值：
 *      无
 **/
static void destory_treeNode_child(htNode *node)
{
    if (node->lchild != NULL)
    {
        destory_treeNode_child(node->lchild);
        free(node->lchild);
        node->lchild = NULL;
    }
    if (node->rchild != NULL)
    {
        destory_treeNode_child(node->rchild);
        free(node->rchild);
        node->rchild = NULL;
    }
}
/**
 *  功  能：
 *      销毁霍夫曼树 
 *  参  数：
 *      hTree ：要销毁的霍夫曼树
 *  返回值：
 *      无
 **/
void destory_huffmanTree(htTree *hTree)
{
    if (hTree == NULL)
        return;
    if (hTree->root == NULL)
        return;

    if (hTree->root->lchild == NULL)
        return;

    destory_treeNode_child(hTree->root);
    free(hTree->root);
    hTree->root = NULL;

    if (hTree != NULL)
        free(hTree);

    hTree = NULL;
}

/**
 *  功  能：
 *      递归遍历霍夫曼树，找到对应的叶子节点（字符串中的字符）
 *      从霍夫曼树的根节点开始，往左边走设置为‘0’，王右边走设置为‘1’
 *      直到找到对应的叶子节点
 *  参  数：
 *      tree  ：霍夫曼树的根节点 
 *      table ：带索引的表
 *      level ：目前位于第k层
 *      code  ：保存字符串（0，或者1）
 *  返回值：
 *      无
 **/
static void traverse_huffmanTree(htNode *tree, hlTable **table, int level, char *code)
{
    // 就是叶子节点
    if (tree->lchild == NULL && tree->rchild == NULL)
    {
        code[level] = '\0'; // 编码的字符串的结束标识
        // 声明一个节点
        hlNode *node = (hlNode *)malloc(sizeof(hlNode));
        node->code = (char *)malloc(sizeof(char) * (strlen(code) + 1));

        //填充，
        strcpy(node->code, code);
        node->symbol = tree->symbol;
        node->next = NULL;

        // first指针指向第一个节点，last指向下面的每一个
        // first为NULL说明当前没有节点，现在的节点就是第一个节点，也是最后一个节点
        if ((*table)->first == NULL)
        {
            (*table)->first = node; // table的第一个节点为当前的节点
            (*table)->last = node;
        }
        else // 如果已经有节点的话，和链表差不多
        {
            (*table)->last->next = node;
            (*table)->last = node;
        }
    }
    // 如果存在左孩子，不是叶子节点，需要找到叶子节点，也就是原本字符所在的位置
    if (tree->lchild != NULL)
    {
        code[level] = '0'; // 左分支上用0来表示编码
        // 递归判断是否存在左孩子，level+1 层
        traverse_huffmanTree(tree->lchild, table, level + 1, code);
    }
    // 如果存在右孩子
    if (tree->rchild != NULL)
    {
        code[level] = '1'; // 右分支上用1来表示编码
        // 递归判断是否存在右孩子，level+1 层
        traverse_huffmanTree(tree->rchild, table, level + 1, code);
    }
}

/**
 *  功  能：
 *      创建霍夫曼树下各个叶子节点（出现字符）的对应的编码的表格
 *      从霍夫曼树的根节点开始，往左边走设置为‘0’，王右边走设置为‘1’
 *      直到找到对应的叶子节点
 *  参  数：
 *      huffmanTree ：霍夫曼树的根节点 
 *  返回值：
 *      无
 **/
hlTable *build_huffmanCodingTable(htTree *huffmanTree)
{
    hlTable *ret = NULL;

    if (huffmanTree == NULL)
        goto ERROR_END;

    // 创建一个表，带索引的表
    hlTable *table = (hlTable *)malloc(sizeof(hlTable));
    if (table == NULL)
        goto ERROR_END;

    table->first = NULL;
    table->last = NULL;

    char code[256] = {0};
    int level = 0;

    // 霍夫曼树的根节点，带索引的表，目前位于第level层，保存字符串（0，或者1）
    traverse_huffmanTree(huffmanTree->root, &table, level, code);

    ret = table;

ERROR_END:
    return ret;
}

/**
 *  功  能：
 *      销毁霍夫曼树下各个叶子节点（出现字符）的对应的编码的表格
 *  参  数：
 *      table ：要销毁的表 
 *  返回值：
 *      无
 *  说  明：
 *      此释放不是很完美，可能还存在问题
 **/
void destory_huffmanCodingTable(hlTable *table)
{
    if (table == NULL)
        return;

    hlNode *temp = table->first;
    while (temp != NULL)
    {
        free(temp->code);
        temp->code = NULL;
        free(temp);
        temp = temp->next;
    }

    free(table);
    table = NULL;
}
/**
 *  功  能：
 *      对输入字符串进行编码
 *      编码的依据是前面输入的字符串所创建的霍夫曼树
 *  参  数：
 *      table ：根据霍夫曼树创建的字符串优先级表格
 *      str   ：要进行编码的字符串
 *      out   ：编码输出
 *          注意：请将定义的out的空间设置足够大
 *  返回值：
 *      无
 **/
void huffman_enCoding_String(hlTable *table, char *str, char *out)
{
    if (table == NULL || str == NULL || out == NULL)
        goto ERROR_END;

    int i = 0, len = 0;

    for (i = 0; str[i] != '\0'; i++)
    {
        hlNode *traversal = table->first;
        while (traversal->symbol != str[i])
            traversal = traversal->next;
        sprintf(out + len, "%s ", traversal->code); // printf("%s ", traversal->code);
        len += strlen(traversal->code) + 1;
    }

ERROR_END:
    return;
}

/**
 *  功  能：
 *      对输入字符串进行编码
 *      解码的依据是前面输入的字符串所创建的霍夫曼树
 *  参  数：
 *      tree ：霍夫曼树创
 *      str  ：要进行解码的编码字符串
 *      out  ：编码输出
 *          注意：请将定义的out的空间设置足够大
 *  返回值：
 *      无
 **/
void huffman_deCoding_String(htTree *tree, char *str, char *out)
{
    int i = 0, len = 0;
    if (tree == NULL || str == NULL || out == NULL)
        goto ERROR_END;

    htNode *traversal = tree->root;

    for (i = 0; str[i] != '\0'; i++)
    {
        // 说明是叶子节点，正好就是目前这个编码对应的字符
        if (traversal->lchild == NULL && traversal->rchild == NULL)
        {
            sprintf(out + len, "%c", traversal->symbol); //printf("%c", traversal->symbol);
            traversal = tree->root;
            len += 1;
        }
        // 如果编码为 '0', 则说明是要往左边走
        if (str[i] == '0')
            traversal = traversal->lchild;
        // 如果编码为 '1', 则说明是要往右边走
        if (str[i] == '1')
            traversal = traversal->rchild;
        // 如果出现既不是0也不是1的字符串，那就只能是出错了
        if (str[i] != '0' && str[i] != '1') // printf("The input sting is not coded correctly!\n");
            goto ERROR_END;
    }
    // 如果下面的田间判断成立，那么说明要解码的编码是正好的，最后一个字符解码出来，但是没有进入上面的叶子节点判断中
    if (traversal->lchild == NULL && traversal->rchild == NULL)
        sprintf(out + len, "%c", traversal->symbol);
    else // 进入到这儿，说明编码后面有一些是未能成功解码的
        printf("Some codes were not successfully decoded!\n");

ERROR_END:
    printf("\n");
}

func_huffmanTree fhuffmanTree = {
    build_huffmanTree,
    build_huffmanCodingTable,
    huffman_enCoding_String,
    huffman_deCoding_String,
    destory_huffmanTree,
    destory_huffmanCodingTable};
